using System;
using System.Collections.Generic;
using System.Linq;


namespace IRobot
{
    public class MeRobot
    {
        public readonly int RoomSize;
        public readonly int DirtyCellsAllowed;
        private readonly RobotMove[] Moves;
        private int _stepsCount;

        public MeRobot(int roomSize, int dirtyCellsAllowed)
        {
            RoomSize = roomSize;
            DirtyCellsAllowed = dirtyCellsAllowed;

            Moves = new[]
            {
                new RobotMove(0, -3, -1, true, 2), //0
                new RobotMove(1, -1, -3, false, 7), //1
                new RobotMove(2, 3, -1, true,0), //2
                new RobotMove(3, 1, -3, false, 3), //3
                new RobotMove(4, 3, 1, true, 6), //4
                new RobotMove(5, 1, 3, false, 3), //5
                new RobotMove(6, -3, 1, true, 4), //6
                new RobotMove(7, -1, 3, false, 1), //7
            };
        }

        public void Clean(SearchType searchType)
        {

            Console.WriteLine("\n---------------------------\n Clean {0}  \n---------------------------\n\n", searchType);


            //init room cells
            var roomCells = new int[RoomSize, RoomSize];
            for (var i = 0; i < RoomSize; i++)
                for (var j = 0; j < RoomSize; j++)
                    roomCells[i, j] = 1;
            roomCells[0, 0] = 0;

            var startState = new State(0, 0, roomCells, null, null, 1);
            State solution;
            _stepsCount = 0;
            switch (searchType)
            {
                case SearchType.DFS:
                    solution = CleanDfs(startState);
                    break;
                case SearchType.BFS:
                    solution = CleanBfs(startState);
                    break;
                case SearchType.BEFS:
                    solution = CleanBefs(startState);
                    break;
                default:
                    throw new ArgumentOutOfRangeException("searchType");
            }

            PrintSolution(solution);
        }

        private void PrintSolution(State lastState)
        {
            if (lastState == null)
            {
                Console.WriteLine("There is no solution for this problem\n");
                return;
            }

            var dirtyCount = GetDirtyCellsCount(lastState);
            Console.WriteLine("Cells left dirty:{0}\n", dirtyCount);
            Console.WriteLine("Number of nodes that were expanded :{0}\n", _stepsCount);

            //we have the solution, but have it from leaf to root
            //using stack to get the opposite order
            State s = lastState;
            var stack = new Stack<State>();
            while (s != null)
            {
                stack.Push(s);
                s = s.Parent;
            }

            //print states in the correct order
            while (stack.Count > 0)
            {
                Console.WriteLine(stack.Pop());
            }
        }

        private List<State> GetPossibleNextStates(State currentState)
        {
            var states = new List<State>();

            foreach (var move in Moves)
            {
                State chState;
                bool isPossible = IsPossibleMove(currentState, move, out chState);
                if (!isPossible) continue;

                states.Add(chState);
            }

            return states;
        }

        private List<State> GetPossibleNextStatesSortedByHeuristic(State currentState)
        {
            List<State> possibleNextStates =  GetPossibleNextStates(currentState);

            foreach (var state in possibleNextStates)
            {
                //heuristic = 1 if next move is symmetric to current move; 
                //            2 else
                int heuristic = 2;
                if (currentState.Move!=null && currentState.Move.SymmetricMoveId==state.Move.Index)
                    heuristic = 1;

                state.heuristic = heuristic;
            }

            List<State> newList = possibleNextStates.OrderBy(s=>s.heuristic).ToList();

            return newList;
        }

        private List<Cell> GetNewCleanCells(State state, RobotMove move)
        {
            var cleanCells = new List<Cell>();
            var currentCell = new Cell(state.X, state.Y);
            if (move.StartHorizontal)
            {
                currentCell = AddCleanHorizontal(currentCell, cleanCells, move);
                AddCleanVertical(currentCell, cleanCells, move);
            }
            else
            {
                currentCell = AddCleanVertical(currentCell, cleanCells, move);
                AddCleanHorizontal(currentCell, cleanCells, move);
            }

            return cleanCells;
        }

        private Cell AddCleanVertical(Cell currentCell, List<Cell> cleanCells, RobotMove move)
        {
            var delta = move.Y > 0 ? 1 : -1;
            for (int i = 0; i < Math.Abs(move.Y); i++)
            {
                var cell = new Cell(currentCell.X, currentCell.Y + delta);
                cleanCells.Add(cell);

                currentCell = cell;
            }
            return currentCell;
        }

        private Cell AddCleanHorizontal(Cell currentCell, List<Cell> cleanCells, RobotMove move)
        {
            var delta = move.X > 0 ? 1 : -1;

            for (int i = 0; i < Math.Abs(move.X); i++)
            {
                var cell = new Cell(currentCell.X + delta, currentCell.Y);
                cleanCells.Add(cell);

                currentCell = cell;
            }
            return currentCell;
        }

        public bool IsGoal(State state)
        {
            var dirtyCellsCount = GetDirtyCellsCount(state);
            return (dirtyCellsCount <= DirtyCellsAllowed);
        }

        private int GetDirtyCellsCount(State state)
        {
            var dirtyCellsCount = (RoomSize * RoomSize) - state.CleanCount;
            return dirtyCellsCount;
        }

        public bool IsPossibleMove(State state, RobotMove move, out State chState)
        {
            var targetX = state.X + move.X;
            var targetY = state.Y + move.Y;
            chState = null;

            //out of border
            if (targetX < 0 || targetX > RoomSize - 1 ||
                targetY < 0 || targetY > RoomSize - 1)
                return false;

            var roomCells = (int[,])state.RoomCells.Clone();
            var moveCells = GetNewCleanCells(state, move);
            foreach (var cell in moveCells)
            {
                //check if cell is already clean
                if (roomCells[cell.X, cell.Y] == 0)
                    return false;

                roomCells[cell.X, cell.Y] = 0;
            }

            int cleanCount = state.CleanCount + Math.Abs(move.X) + Math.Abs(move.Y);
            chState = new State(targetX, targetY, roomCells, state, move, cleanCount);
            return true;
        }

        private State CleanDfs(State currentState)
        {
            if (IsGoal(currentState))
                return currentState;

            List<State> possibleNextStates = GetPossibleNextStates(currentState);

            foreach (var state in possibleNextStates)
            {
                _stepsCount++;
                State result = CleanDfs(state);

                if (result != null) 
                    return result;
            }
            
            return null;

        }

        private State CleanBfs(State startState)
        {
            var toVisit = new Queue<State>();

            //initialization
            toVisit.Enqueue(startState);

            while (toVisit.Count != 0)
            {
                State currentState = toVisit.Dequeue();
                if (IsGoal(currentState))
                    return currentState;

                List<State> possibleNextStates = GetPossibleNextStates(currentState);
                foreach (var state in possibleNextStates)
                    toVisit.Enqueue(state);

                _stepsCount++;
            }
            return null;
        }

        private State CleanBefs(State currentState)
        {
            if (IsGoal(currentState))
                return currentState;

            List<State> possibleNextStatesSortedByHeuristic = GetPossibleNextStatesSortedByHeuristic(currentState);

            foreach (var state in possibleNextStatesSortedByHeuristic)
            {
                _stepsCount++;
                State result = CleanBefs(state);

                if (result != null)
                    return result;
            }

            return null;

        }
    }
}